The present invention concerns a two priority fair distributed round robin protocol for a network having cascaded hubs.
Various topologies may be used to connect network stations together in a local area network. In one topology, a hub may be directly connected to several network stations, called end nodes. Each end node connected to the hub communicates to other end nodes connected to the hub by sending network packets to the hub which the hub forwards to one or more of the other end nodes.
When, at one time, more than one end node desires to forward network packets to the hub, some form of arbitration scheme is necessary to assure that no transmissions are lost or garbled since only one packet can be transmitted over the network at any one time. When there is only a single hub in the local area network, the hub can, with limited overhead, enforce a fair and effective arbitration scheme.
It is desirable, however, to allow for expansion of a hub network by adding additional hubs. This is done, for example, by cascading the hubs. See, U.S. Pat. No. 4,716,408 issued to Stuart O'Connor, et al. for Data Transmission System of the Star Type with Enablement Passing.
However, prior arbitration schemes could not simultaneously provide priorities, cascaded hubs and both fair and effective arbitration. What is meant by a fair arbitration scheme is one which treats requests by all end nodes in an even-handed manner. That is, no end nodes are put at a disadvantage because they are connected to one hub and not to another hub. What is meant by an effective arbitration scheme is one in which network throughput is maximized. That is, when end nodes are contending for network resources, the amount of time the network is idle or in arbitration is minimized.
Fair and efficient arbitration schemes for a network with cascaded hubs have generally handled requests within only a single priority level. See, for example, U.S. Pat. No. 5,018,139, cited above. When requests with a second priority level have been allowed, this has resulted in arbitration schemes which are less fair and/or less efficient. For example, such two priority arbitration schemes have handled only one network packet per hub per cycle. This results in end nodes connected to hubs with fewer active end nodes having a larger share of network bandwidth than end nodes on hubs with many active end nodes. Additionally, arbitration schemes which handle only one network packet per hub per cycle require more overhead for each network packet sent across the network. This reduces network throughput.